import java.awt.*;
import java.util.ArrayList;

public class walkMaze {
    private static int[][] maze =    //0代表通路，1代表墙
            {{1,1,1,1,1,1,1,1,1,1},
                    {1,0,1,1,0,0,0,1,0,1},
                    {1,0,0,0,0,1,0,0,0,1},
                    {1,1,1,0,1,0,0,1,1,1},
                    {1,0,0,0,1,1,1,0,0,1},
                    {1,0,1,1,0,0,0,0,1,1},
                    {1,0,0,0,0,1,1,1,0,1},
                    {1,1,1,0,1,0,0,0,0,1},
                    {1,0,0,0,0,0,1,1,0,1},
                    {1,1,1,1,1,1,1,1,1,1}};
    private static ArrayList<Point> route = new ArrayList<>();
private static boolean isWalk(int[][] maze,Point currentPoint){
        int x = currentPoint.x;
        int y = currentPoint.y;
        if (maze[y][x+1]!=1 && maze[y][x+1]!=-1){//往右走
            route.add(new Point(x+1,y));
            return true;
        }
        if (maze[y+1][x]!=1 && maze[y+1][x]!=-1){
            route.add(new Point(x,y+1));//往下走
            return true;
        }
        if (maze[y][x-1]!=1 && maze[y][x-1]!=-1){
            route.add(new Point(x-1,y));//往左走
            return true;
        }
        if (maze[y-1][x]!=1 && maze[y-1][x]!=-1){
            route.add(new Point(x,y-1));//往上走
            return true;
        }
        return false;
    }
    private static boolean maze(int[][] maze,Point enter){
        maze[enter.y][enter.x]=-1;
        route.add(enter);
        while (!route.isEmpty()){
            while (isWalk(maze,enter)){
                enter = route.get(route.size()-1);
                if (enter.x==8 && enter.y==8){ //判断是否是出口
                    return true;
                }else{
                    maze[enter.y][enter.x]=-1;//标记已走过的位置为-1
                }
            }
            //判断是否通路
            route.remove(route.size()-1);
            enter = route.get(route.size()-1);
        }
        return false;
    }
    public static void main(String[] args) {
        System.out.println("迷宫如下：");
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze.length; j++) {
                System.out.print(maze[i][j]+"  "); //打印迷宫
            }
            System.out.println();
        }
        //走迷宫
        boolean flag = maze(walkMaze.maze, new Point(1, 1));
        if (flag){
            System.out.println("路线如下：");
            for (int i = 0; i < route.size(); i++) {
                System.out.print("("+route.get(i).x+","+route.get(i).y+")");
                if (i!=route.size()-1){
                    System.out.print(">");
                }
            }
        }
    }
}

